/**
 * 面试题55-2：平衡二叉树
 */
public class Offer_55_II {
    /**
     * 方法二：自底向上的递归
     * <p>
     * 对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    /**
     * 如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1
     */
    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 方法一：自顶向下的递归
     * <p>
     * 对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，
     * 
     * 再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡
     * <p>
     * 时间复杂度：O(n^2)
     * <p>
     * 空间复杂度：O(n)
     */
    public boolean isBalanced1(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced1(root.left) && isBalanced1(root.right);
    }

    /**
     * 计算二叉树的深度
     */
    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}
